﻿package string;

public class 在有序但含有空的数组中查找字符串 {

	public static int getLeftIndex(String[] strs, String m) {
		if (strs == null || m == null || strs.length == 0 || strs.length == 0) {
			return -1;
		}

		int res = 0;
		int left = 0;
		int right = strs.length - 1;
		int middle = 0;
		int i = 0;
		while (left <= right) {
			middle = (left + right) >> 1;
			if (strs[middle] != null && strs[middle].equals(m)) {
				res = middle;
				right = middle - 1;// 继续向左进行遍历
			} else if (strs[middle] != null) {
				// strs[middle]不是null，但也不是要匹配的，这时候要判断字典顺序
				
				if(strs[middle].compareTo(m)<0){
					//strs[middle]比m小,则区域应变成[middle+1,right]
					left  = middle+1;
				}else{
					right = middle-1;
				}
			}else{
				//当strs[middle]是空的时候，需要在左右各自进行遍历
				i = middle;
				while(strs[i]==null&&--i>=left);//向左找到第一个不是null的位置
				
				//如果已经遍历到最左边了，或者左侧出现的最右的字符串已经比m要小了，则m不可能出现在[left,middle]
				if(i<left||strs[i].compareTo(m)<0){
					//出现在右边
					left = middle +1;
				}else{
					//否则，将匹配到的字符串和m进行比较
					res = strs[i].equals(m)?i:res;
				}
			}
			
		}
		return res;
	}

	public static void main(String[] args) {
		String[] strs ={null,"a",null,"b",null,"a",null,"c"};
		System.out.println(getLeftIndex(strs,"a"));

	}

}
